import itertools


# 计算重量
def calculate_weight(this_list):
    weight_sum = 0
    for item in this_list:
        weight_sum += item["weight"]
    return weight_sum


# 计算价值
def calculate_value(this_list):
    weight_value = 0
    for item in this_list:
        weight_value += item["value"]
    return weight_value


def exhaustive_method(list_goods, knapsack):
    # 排列组合
    list_result = []
    for i in range(1, len(list_goods) + 1):
        # 算出多少种可能
        combinations = list(itertools.combinations(list_goods, i))
        # 把所有的可能性加入到list_result
        list_result.extend(combinations)

    # 计算最大
    max_value = 0
    max_list = []
    for i in range(len(list_result)):
        # 如果这种组合重量小于150,并且价值大于最大价值，则
        if calculate_weight(list_result[i]) <= knapsack and calculate_value(list_result[i]) >= max_value:
            max_value = calculate_value(list_result[i])
            # 价值一致的物品，加入到max_list
            if max_list and max_value == calculate_value(max_list[0]):
                max_list.append(list_result[i])
            else:
                max_list = [list_result[i]]

    max_list.insert(0, max_value)
    return max_list


if __name__ == "__main__":
    """
    背包M=150
    物品:A    B    C    D    E    F    G
    重量:35   30   60   50   40   10   25
    价值:10   40   30   55   35   40   30
    """
    list1 = [
        {"name": "A", "weight": 35, "value": 10},
        {"name": "B", "weight": 30, "value": 40},
        {"name": "C", "weight": 60, "value": 30},
        {"name": "D", "weight": 50, "value": 55},
        {"name": "E", "weight": 40, "value": 35},
        {"name": "F", "weight": 10, "value": 40},
        {"name": "G", "weight": 25, "value": 30}
    ]

    for item in exhaustive_method(list1, 150):
        print(item)
